π§· ν(Heap)
μ°μ μμ νλ₯Ό μν΄ λ§λ€μ΄μ§ μλ£κ΅¬μ‘°μ΄λ€.
- μ½μ κ³Ό μμ λͺ¨λ μΌλ‘ ν΄κ²°ν μ μλ€.
-
μμ μ΄μ§ νΈλ¦¬μ μΌμ’ μ΄λ€.
- μ¬λ¬ κ° μ€, μ΅λκ°κ³Ό μ΅μκ°μ λΉ λ₯΄κ² μ°Ύμλ΄λλ‘ λ§λ€μ΄μ§ μλ£κ΅¬μ‘°
- λ° μ λ ¬ μν (무쑰건 μ λ ¬λμ΄ μμ νμκ° μλ€.)
- ν νΈλ¦¬λ μ€λ³΅λ κ° νμ© (μ΄μ§ νμ νΈλ¦¬λ μ€λ³΅κ°μ νμ©νμ§ μμ)
μ°μ μμ ν? : μ°μ μμμ κ°λ μ νμ λμ ν μλ£κ΅¬μ‘°λ‘, λ°μ΄ν°λ€μ΄ μ°μ μμλ₯Ό κ°μ§κ³ μκ³ μ΄μ λ°λΌ μ°μ μμκ° λμ λ°μ΄ν°κ° λ¨Όμ λκ°κ² λλ ꡬ쑰μ΄λ€.
- μ°μ μμ νλ λ°°μ΄, μ°κ²°λ¦¬μ€νΈ, νμΌλ‘ ꡬνν μ μλλ°, κ·Έ μ€ νμ΄ κ°μ₯ ν¨μ¨μ μ΄λ€.
μμ μ΄μ§ νΈλ¦¬? : λ Έλλ₯Ό μ½μ ν λ, μΌμͺ½λΆν° μ°¨λ‘λλ‘ μ½μ νλ νΈλ¦¬μ΄λ€.
πͺ μ’ λ₯
μ΅λ ν(Max Heap)
- λΆλͺ¨ λ Έλμ ν€ κ°μ΄ μμ λ Έλμ ν€ κ°λ³΄λ€ ν¬κ±°λ κ°μ μμ μ΄μ§ νΈλ¦¬
μ΅μ ν(Min Heap)
- λΆλͺ¨ λ Έλμ ν€ κ°μ΄ μμ λ Έλμ ν€ κ°λ³΄λ€ μκ±°λ κ°μ μμ μ΄μ§ νΈλ¦¬
πͺ ꡬν
νμ μ μ₯νλ νμ€μ μλ£κ΅¬μ‘°λ λ°°μ΄ μ΄λ€.
- ꡬνμ μ½κ² νκΈ° μν΄ λ°°μ΄μ 첫 λ²μ§Έ μΈλ±μ€μΈ 0μ μ¬μ©λμ§ μλλ€.
- νΉμ μμΉμ λ Έλ λ²νΈλ μλ‘μ΄ λ Έλκ° μΆκ°λμ΄λ λ³νμ§ μλλ€.
λΆλͺ¨ λ Έλμ μμ λ Έλμ κ΄κ³
μΌμͺ½ μμ index = (λΆλͺ¨ index) * 2
μ€λ₯Έμͺ½ μμ index = (λΆλͺ¨ index) * 2 + 1
λΆλͺ¨ index = (μμ index) / 2
μ½μ
- νμ μλ‘μ΄ μμκ° λ€μ΄μ€λ©΄, μΌλ¨ μλ‘μ΄ λ Έλλ₯Ό νμ λ§μ§λ§ λ Έλμ μ½μ
- μλ‘μ΄ λ Έλλ₯Ό λΆλͺ¨ λ Έλλ€κ³Ό κ΅ν
// μ΅λ νμ μ½μ
ꡬν
void insertMaxHeap(int x) {
// ν ν¬κΈ°λ₯Ό μ¦κ°μν€κ³ , λ§μ§λ§ λ
Έλμ μ½μ
maxHeap[++heapSize] = x;
for (int i = heapSize; i > 1; i/=2) {
// λ§μ§λ§ λ
Έλκ° μμ μ λΆλͺ¨ λ
Έλλ³΄λ€ ν¬λ©΄ swap
if (maxHeap[i/2] < maxHeap[i]) swap(i/2, i);
else break;
}
}
μμ
- μ΅λ νμμ μ΅λκ°μ λ£¨νΈ λ Έλμ΄λ―λ‘ λ£¨νΈ λ Έλκ° μμ λ¨
- μμ λ λ£¨νΈ λ Έλμλ νμ λ§μ§λ§ λ Έλλ₯Ό κ°μ Έμ΄
- νμ μ¬κ΅¬μ±(
heapify)
// μ΅λ ν μμ ꡬν
int deleteMaxHeap() {
if (heapSize == 0) return 0;
// λ£¨νΈ λ
Έλμ κ°μ μ μ₯νκ³ , λ§μ§λ§ λ
Έλ κ°μ 루νΈλ‘ μ΄λν ν ν ν¬κΈ°λ₯Ό μ€μ¬ λ§μ§λ§ λ
Έλλ₯Ό 0μΌλ‘ μ΄κΈ°ν
int item = maxHeap[1];
maxHeap[1] = maxHeap[heapSize];
maxHeap[heapSize--] = 0;
for (int i = 1; i*2 <= heapSize;) {
// λ§μ§λ§ λ
Έλκ° μΌμͺ½ λ
Έλμ μ€λ₯Έμͺ½ λ
Έλλ³΄λ€ ν¬λ©΄ μ΅λ νμ΄λ―λ‘ μ’
λ£
if (maxHeap[i] > maxHeap[i*2] && maxHeap[i] > maxHeap[i*2+1]) break;
// μμ λ
Έλκ° λ ν° κ²½μ°, κ΅νν ν, iλ₯Ό λ³κ²½
else if (maxHeap[i*2] > maxHeap[i*2+1]) {
swap(i, i*2);
i *= 2;
} else {
swap(i, i*2+1);
i = i*2+1;
}
}
return item;
}